package sword.chapter4LinkList;

import leetcode.t4LinkedList.ListNode;

/**
 * 两个链表的第一个重合结点
 * 1. 消除差值
 *
 * @author K
 * @date 2021-11-24 21:51
 */
public class S23GetIntersectionNode {
    public static void main(String[] args) {
        ListNode nodeA = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        nodeA.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        ListNode nodeB = new ListNode(7);
        ListNode node8 = new ListNode(8);
        nodeB.next = node8;
        node8.next = node4;
//        BaseLinkList result = s23(nodeA, nodeB);
        ListNode result = s23t(nodeA, nodeB);
        System.out.println();
    }

    public static ListNode s23t(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode a = headA;
        ListNode b = headB;
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }

    public static ListNode s23(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        int aLength = 0;
        int bLength = 0;
        while (headA != null || headB != null) {
            if (headA != null) {
                aLength++;
                headA = headA.next;
            }
            if (headB != null) {
                bLength++;
                headB = headB.next;
            }
        }
        int c = Math.abs(aLength - bLength);

        if (aLength > bLength) {
            for (int i = 0; i < c; i++) {
                if (a == null) {
                    return null;
                }
                a = a.next;
            }
        } else {
            for (int i = 0; i < c; i++) {
                if (b == null) {
                    return null;
                }
                b = b.next;
            }
        }

        while (a != b) {
            if (a == null || b == null) {
                return null;
            }
            a = a.next;
            b = b.next;
        }
        return a;
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        int aLength = 0;
        int bLength = 0;
        while (headA != null || headB != null) {
            if (headA != null) {
                aLength++;
                headA = headA.next;
            }
            if (headB != null) {
                bLength++;
                headB = headB.next;
            }
        }
        int c = Math.abs(aLength - bLength);

        if (aLength > bLength) {
            for (int i = 0; i < c; i++) {
                if (a == null) {
                    return null;
                }
                a = a.next;
            }
        } else {
            for (int i = 0; i < c; i++) {
                if (b == null) {
                    return null;
                }
                b = b.next;
            }
        }

        while (a != b) {
            if (a == null || b == null) {
                return null;
            }
            a = a.next;
            b = b.next;
        }
        return a;
    }
}
